package com.banana.linkedlist;

import org.junit.jupiter.api.Test;

/**
 * 约瑟夫问题 -> 运用环形单向链表解决
 */
public class JosephuDemo {
    @Test
    void testFirst() {
        CircleSingleLinkedList list = new CircleSingleLinkedList();
        list.addBoy(10);
        list.list();
        System.out.println("当前小孩个数：" + list.size());
    }
}

/**
 * 创建一个环形单向链表
 */
class CircleSingleLinkedList {
    // 创建一个first节点，当前无编号
    private Boy first = new Boy(-1);

    public void  addBoy(int nums) {
        if (nums < 1) {
            System.out.println("添加的小孩至少为1个");
            return;
        }
        // 定义一个辅助指针，表示当前的节点
        Boy cur = null;
        // 遍历添加
        for (int i = 1; i <= nums; i++) {
            Boy boy = new Boy(i);
            if (i == 1) {
                // 首个节点
                first = boy;
                first.setNext(first);
                cur = first;
            }else {
                cur.setNext(boy); // 当前的尾节点的next指向添加节点
                boy.setNext(first); // 新的尾节点指向头节点
                cur = boy; // 辅助指针重新指向新尾节点
            }
        }
    }

    public void list() {
        if (first == null) {
            System.out.println("当前没有小孩");
            return;
        }
        Boy cur = first;
        while (true) {
            System.out.printf("小孩的编号是%d\n",cur.getNo());
            if (cur.getNext() == first) {
                break;
            }
            // 指针后移
            cur = cur.getNext();
        }
    }

    public int size() {
        int count = 0;
        if (first == null) {
            return count;
        }
        Boy cur = first;
        while (true) {
            count++;
            if (cur.getNext() == first) {
                break;
            }
            cur = cur.getNext();
        }
        return count;
    }
}

/**
 * 创建一个Boy类，表示节点
 */
class Boy {
    private int no;
    private Boy next;

    public Boy(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }
}